package com.yan.programercode.chapter_1.question_7;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * 有一个整形数组arr和一个大小为w的窗口从数组的最左边滑动到最右边，窗口每次向右边滑动一个位置
 * 
 * 例如，数组为[4, 3, 5, 4, 3, 3, 6, 7]，窗口大小为3时
 * 
 * [4, 3, 5], 4, 3, 3, 6, 7    窗口中最大值为5
 * 4, [3, 5, 4], 3, 3, 6, 7    窗口中最大值为5
 * 4, 3, [5, 4, 3], 3, 6, 7    窗口中最大值为5
 * 4, 3, 5, [4, 3, 3], 6, 7    窗口中最大值为4
 * 4, 3, 5, 4, [3, 3, 6], 7    窗口中最大值为5
 * 4, 3, 5, 4, 3, [3, 6, 7]    窗口中最大值为7
 * 
 * 如果数组长度为你，窗口大小为w，则一共产生n-w+1个窗口的最大值
 * 
 * 请实现一个函数
 * - 输入：整形数组arr，窗口大小w
 * - 输出：一个长度为n-w+1的整形数组res，，res[i]表示每一个窗口中状态下的最大值
 * 
 * @author Yan
 *
 */
public class WindowMaxValueArray {

	public static void main(String[] args) {
		int[] arr = {4, 3, 5, 4, 3, 3, 6, 7};
		int w = 3;
		System.out.println(Arrays.toString(getMaxWindow(arr, w)));
	}
	
	public static int[] getMaxWindow(int[] arr, int w){
		if(arr == null || w < 1 || arr.length < w){
			return null;
		}
		LinkedList<Integer> qmax = new LinkedList<Integer>();
		int[] res = new int[arr.length - w + 1];
		int index = 0;
		for(int i=0;i<arr.length;i++){
			while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]) {
				// pollLast()
				// Retrieves and removes the last element of this list, or returns null if this list is empty.
				qmax.pollLast();
			}
			qmax.addLast(i);
			
			// peekFirst()
			// Retrieves, but does not remove, the first element of this list, or returns null if this list is empty.
			if(qmax.peekFirst() == i - w){
				qmax.pollFirst();
			}
			if(i >= w - 1){
				res[index++] = arr[qmax.peekFirst()];
			}
		}
		return res;
	}

}
